#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <stack>
using namespace std;


//class Solution {
//public:
//    string longestPalindrome(string s) {
//        unordered_map<char, vector<int>> hash;
//        int n = s.size();
//        for (int i = 0; i < n; i++)
//        {
//            hash[s[i]].push_back(i);
//        }
//        int left = 0;
//        string s1;
//        int my_max = 0;
//        while (left < n)
//        {
//            int rn = hash[s[left]].size();
//            for (int i = 0; i < rn; i++)
//            {
//                int right = hash[s[left]][i];
//                if (right >= left)
//                {
//                    int p = left;
//                    int r = right;
//                    int k = 0;
//                    while (p < right)
//                    {
//                        if (s[p] != s[right])
//                        {
//                            break;
//                        }
//                        k += 2;
//                        p++;
//                        right--;
//                    }
//                    if (p == right)
//                    {
//                        k++;
//                        if (k > my_max)
//                        {
//                            s1 = s.substr(left, k);
//                            my_max = k;
//                        }
//                    }
//                    else if (p > right)
//                    {
//                        if (k > my_max)
//                        {
//                            s1 = s.substr(left, k);
//                            my_max = k;
//                        }
//                    }
//                }
//            }
//            left++;
//        }
//        return s1;
//    }
//};
//
//
//class Solution {
//public:
//    pair<int, int> expandAroundCenter(const string& s, int left, int right) {
//        while (left >= 0 && right < s.size() && s[left] == s[right])
//        {
//            --left;
//            ++right;
//        }
//        return { left + 1, right - 1 };
//    }
//
//    string longestPalindrome(string s) {
//        int start = 0, end = 0;
//        for (int i = 0; i < s.size(); ++i)
//        {
//            auto [left1, right1] = expandAroundCenter(s, i, i);
//            auto [left2, right2] = expandAroundCenter(s, i, i + 1);
//            if (right1 - left1 > end - start)
//            {
//                start = left1;
//                end = right1;
//            }
//            if (right2 - left2 > end - start)
//            {
//                start = left2;
//                end = right2;
//            }
//        }
//        return s.substr(start, end - start + 1);
//    }
//};


class Solution {
public:
    pair<int, int> My_Long(string& s, int l, int r, int n)
    {
        int left = l;
        int right = r;
        int k = 0;
        while (left >= 0 && right < n)
        {
            if (s[left] != s[right])
            {
                break;
            }
            if (left == right)
            {
                k++;
            }
            else
            {
                k += 2;
            }
            left--;
            right++;
        }
        return pair<int, int>(left + 1, k);
    }

    string longestPalindrome(string s) {
        int n = s.size();
        pair<int, int> k = { 0,1 };
        for (int i = 0; i < n; i++)
        {
            auto p = My_Long(s, i, i, n);
            auto q = My_Long(s, i, i + 1, n);
            if (p.second > k.second)
            {
                k = p;
            }
            if (q.second > k.second)
            {
                k = q;
            }
        }
        return s.substr(k.first, k.second);
    }
};

//int main()
//{
//    Solution ms;
//    string s = "babad";
//    cout << ms.longestPalindrome(s) << endl;
//    return 0;
//}

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxans = 0;
        stack<int> stk;
        stk.push(-1);
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == '(')
            {
                stk.push(i);
            }
            else
            {
                stk.pop();
                if (stk.empty())
                {
                    stk.push(i);
                }
                else
                {
                    maxans = max(maxans, i - stk.top());
                }
            }
        }
        return maxans;
    }
};